package day_2022_12_to_3.year2023;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2023/03/28 21:41
 **/
public class Day3_28_Num1092 {
    class Solution {
        public String shortestCommonSupersequence(String str1, String str2) {
            // 最长公共子序列

            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();

            // str1 和 str2 的最短公共父序列, 需要满足 至少是 str1 和 str2的最大长度,然后在此基础上 进行另一个短字符串的穿插赋值
            // -> 在长的字符串中 添加字符, 使得长的字符串可以作为 str1 的 父序列
            // -> 求 str1 和 str2 的最长公共子序列, 得到的结果 在 较长的字符串后面 添加余下的字符

            // 求 str1 和 str2 的最长公共子序列 -> 动态规划
            int[][] dp = new int[chars1.length + 1][chars2.length + 1];
            String[][] dpStr = new String[chars1.length + 1][chars2.length + 1];
            for (String[] strings : dpStr) {
                Arrays.fill(strings, "");
            }
            // 动态转移方程: c1[i] == c2[j] ? dp[i][j] + 1 : Math.max(dp[i+1][j],dp[i][j+1]);
            // 如何记录最长公共子序列是什么 ?
            for (int i = 0; i < chars1.length; i++) {
                for (int j = 0; j < chars2.length; j++) {
                    if (dp[i + 1][j] > dp[i][j + 1]) {
                        dp[i + 1][j + 1] = dp[i + 1][j];
                        dpStr[i + 1][j + 1] = dpStr[i + 1][j];
                    } else {
                        dp[i + 1][j + 1] = dp[i][j + 1];
                        dpStr[i + 1][j + 1] = dpStr[i][j + 1];
                    }
                    if (chars1[i] == chars2[j]) {
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                        dpStr[i + 1][j + 1] = dpStr[i][j] + chars1[i];
                    }

                }
            }

//        for (int i = 0; i < dp.length; i++) {
//            System.out.println(Arrays.toString(dp[i]));
//            System.out.println(Arrays.toString(dpStr[i]));
//        }


            String t = dpStr[chars1.length][chars2.length];

            char[] tt = t.toCharArray();

            char[] child, parent;
            if (chars1.length > chars2.length) {
                child = chars2;
                parent = chars1;
            } else {
                child = chars1;
                parent = chars2;
            }
            // 记录最长公共子序列 在str1 和 str2 中的占位情况
            boolean[] visit1 = new boolean[child.length];
            boolean[] visit2 = new boolean[parent.length];
            int idx1 = 0;
            int idx2 = 0;
            for (char c : tt) {
                while (c != child[idx1]){
                    idx1 ++;
                }
                visit1[idx1] = true;
                idx1++;
                while (c != parent[idx2]){
                    idx2 ++;
                }
                visit2[idx2] = true;
                idx2++;
            }

            // 根据 visit 进行数据填充
            StringBuilder sb = new StringBuilder(new String(parent));
            // visit1 和 visit2 遍历
            int ansIdx = 0;
            idx2 = 0;
            for (int i = 0; i < child.length; i++) {
                if (!visit1[i]) {
                    // 需要将该字节 添加到字符串中
                    sb.insert(ansIdx + idx2, child[i]);
                    ansIdx++;
                }else {
                    // 该字符被引用,
                    while (!visit2[idx2]){
                        idx2 ++;
                    }
                    idx2 ++;
                }
            }

            return sb.toString();
        }
    }
}